def fibonacci(n: int) -> int:
    """
    斐波那契数列，使用幂乘及分治策略。
    """
    if n < 2:
        return n

    q = [[1, 1], [1, 0]]
    res = matrix_pow(q, n - 1)
    return res[0][0]


def matrix_multiply(a: list[list[int]], b: list[list[int]]) -> list[list[int]]:
    c = [[0, 0], [0, 0]]
    for i in range(2):
        for j in range(2):
            c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j]
    return c


def matrix_pow(a: list[list[int]], n: int) -> list[list[int]]:
    ret = [[1, 0], [0, 1]]
    # 也可用递归；
    while n > 0:
        if n & 1:
            ret = matrix_multiply(ret, a)
        n >>= 1
        a = matrix_multiply(a, a)
    return ret


if __name__ == "__main__":
    print(fibonacci(4000))
